1. Field of the Invention
The present invention relates to collision detection for three-dimensional shapes used in computer graphics and the like and for images of the like that have depth and are obtained with range finders, stereoscopic vision, and the like.
2. Description of the Related Art
For some time, formats for collision detection have been used that employ geometric shapes with computer graphics, CAD, and the like as the format for the detection of contact and mutual interference between bodies and components. An explanation will be given regarding polygon model collision detection in which the three-dimensional shape of a body is approximated by small planes using computer graphics. To detect whether collisions have occurred among polygon models, the detection of collisions between each of the planes (polygons) is carried out for all polygon combinations.
Therefore, an explanation will be given using figures regarding a method for collision detection for two triangular polygons. FIG. 17A shows a state in which two triangular polygons 901 and 902 collide with each other, that is to say, overlap. In order to investigate the overlapping between the polygons, overlapping should be investigated between each line segment of the edges that constitute one of the triangles and the plane of the other triangle.
FIG. 17B shows the state in which one edge 903 of the triangular polygon 902 and the triangular polygon 901 overlap at point 904. Using parameter t, the equations of the straight line of the edge 903 in three-dimensional space can be expressed as                     x        =                  x0          +          it                                    (        1        )                                y        =                  y0          +          jt                                    (        2        )                                          z          =                      z0            +            kt                          ,                            (        3        )            
where x0, y0, and z0 are coordinates of a point on the straight line; and i, j, and k are direction vectors of the straight line on the other hand, the equation of a plane on the triangular polygon 901 can be expressed as
ax+by+cz+d=0,xe2x80x83xe2x80x83(4)
where a, b, and c are normal vectors to the surface, and d is the distance from the origin. Therefore, from Equation 1, Equation 2, Equation 3 and Equation 4, the parameter t of the straight line at the point of intersection 904 can be derived as
t0=xe2x88x92(ax0+by0+cz0+d)/(ai+bj+ck).xe2x80x83xe2x80x83(5)
By means of the substitution of the t that has been derived in Equation 1, Equation 2 and Equation 3, it is possible to derive the coordinates of the point of intersection 904.
Actually, since the point of intersection is calculated only from the plane and straight-line parameters, it is necessary to next investigate whether the point of intersection is within the line segment 903 and the triangular polygon 901. With regard to whether the point of intersection 904 is within the line segment 903, if the parameters of the two end points 905 and 906 of the line segment 903 are made t1 and t2 (t1 less than t2) and the parameter t0 of the point of intersection in Equation 5 is
t1xe2x89xa6t0xe2x80x83xe2x80x83(6)
and
t0xe2x89xa6t2,xe2x80x83xe2x80x83(7)
it can be detected that it is on (within) the line segment.
In addition, with regard to the detection as to whether the point 904 is inside the triangular polygon 901, as is shown in FIG. 17C, line segments are drawn from the point 904 to each of the apex points of the triangular polygon and, and if the total of the acute angles formed by the line segments is 360 degrees, it is detected that the point is inside. As is shown in FIG. 17D, in those cases where it is not 360 degrees, it is detected that the point is outside.
The above detection processing is carried out for the entire group of polygons constituting a model. By this means, two-polygon model collision detection is done.
However, the above-mentioned method has had a problem in that the processing time increases in proportion to the complexity of the three-dimensional shape. With the polygon model, as the shape becomes complex, the number of polygons with which detailed shapes are represented increases, and the number of comparison polygon combinations for the collision detection increases.
In particular, with regard to each of the pixels of an image measured with a range finder or the like, when the collision detection between range images (or depth images) at a given distance from the camera, or between the range images and the polygon models is considered, if the range images are thought of as being composed of rectangular polygons whose number is commensurate with the number of image pixels, collision detections for the combinations of polygons is required in an amount commensurate with the number of the pixels of the image. For example, let us assume that each pixel of a distant image is a rectangular polygon. In a worst-case scenario, an established collision involving a single triangular polygon of another body requires that the point of intersection in Equation 5 be calculated and the two magnitudes from Equations (6) and (7) for detecting the positions inside and outside of line segments be compared the number of times equal to the number of pixels, assuming that the number of sides is three. In addition, for the detection involving the interior of a rectangular polygon, it must be carried out the same number of times as the number of pixels for each of the four apex points.
A method may also be considered where a portion obtained by representing a range image as a plane rather than a polygon for each image is replaced with a large polygon, and the number of polygons is reduced. However, there is a problem in that this increases the processing for the polygon reduction.
In addition, collision detection must involve conversion to a polygon model when such detection involves solid models in which three-dimensional shapes rather than range images are represented as solid bodies whose interiors are filled with matter, as well as boxel models and various other models in which computer graphics other than meta-balls or other such polygon models are used. There has been a problem in that, with the increase of the conversion processing and the differences in the model representation methods, there is an extraordinary increase in the number of polygons with the polygon model for shapes that can be represented simply by other models. As an example of the latter problem, the globe is a fundamental shape for the meta-ball or the like, and can be simply described. However, with the polygon model, many polygons are required to describe a globe that has some degree of smoothness.
An object of the present invention is to allow the collision detection for bodies of complex shapes to be carried out with an amount of processing that is proportionate to the number of pixels of the projected image irrespective of the complexity of the body by carrying out collision detection in which arrays are correlated to each of the pixels of a projected image of a body without a collision detection of geometric shapes such as polygons.
In order to the attain the stated object, the present invention dispenses with the use of collision detection between polygons and entails instead performing collision detection that is independent of the complexity of the body shape by using body regions obtained by projecting bodies subject to collision detection onto the pixels of projected images, and by employing a depth array in which distances from an arbitrary point or plane are arranged for each of the pixels of th e projected images.